//ordinary quicksort
typedef int ElemType;
typedef struct SqNode{
	ElemType key;
	InfoType other;
}SqNode;
typedef	struct SqList{
	SqNode data[m+1];
	int length;
}SqList;
void QuickSort(SqList &L, int bottom, int top, int(*keycmp)(ElemType, ElemType)){
	if (bottom < top){
		L.data[0] = L.data[low];
		int i, j;
		for (i = low, j =top ; i < j; ){
			while (j > i && keycmp(L.data[j].key, L.data[0].key) == 1){
				--j;
			}
			L.data[i] = L.data[j];
			while (j > i && keycmp(L.data[i].key, L.data[0].key) == -1){
				++i;
			}
			L.data[j] = L.data[i];
		}
		L.data[i] = L.data[0];
		QuickSort(L, bottom, i - 1);
		QuickSort(L, i + 1, top);
	}
}
//balanced + space optimalize + worst condition optimalize
typedef int ElemType;
typedef struct SqNode{
	ElemType key;
	InfoType other;
}SqNode;
typedef	struct SqList{
	SqNode data[m+1];
	int length;
}SqList;
int Partition(SqList &L, int bottom, int top){
	L.data[0] = L.data[bottom];
	int i, j;
	for (i = bottom, j = top; i < j; ){
		while (i < j && L.data[j].key >= L.data[0].key) --j;
		L.data[i] = L.data[j];
		while (i < j && L.data[i].key <= L.data[0].key) ++i;
		L.data[j] = L.data[i];
	}
	L.data[i]key = L.data[0];
	return i;
}
void Balance(SqList &L, int bottom, int top){
	int mid = (bottom + top) / 2;
	if (L.data[mid].key > L.data[top].key){
		SwapNode(L, mid, top);
	}
	if (L.data[bottom].key > L.data[top].key){
		SwapNode(L, bottom, top);
	}
	if (L.data[bottom].key > L.data[mid].key){
		SwapNode(L, bottom, mid);
	}
}
void SwapNode(SqList &L, int bottom, int top){
	L.data[0] = L.data[bottom];
	L.data[bottom] = L.data[top];
	L.data[top] = L.data[0];
}
void InsertSort(SqList &L, int bottom, int top){
	for (int i = top; i > bottom; --i){
		int j;
		L.data[0] = L.data[i];
		for (j = i - 1; j >= bottom; --j){
			if (L.data[j].key > L.data[0].key){
				L.data[j+1] = L.data[j];
			}
			else break;
		}
		L.data[j+1] = L.data[0];
	}
}
void QuickSort(SqList &L, int bottom, int top){
	if (top - bottom < SETSIZE){
		InsertSort(L, bottom, top);
	}
	else {
		Balance(L, bottom, top);
		int pivotpos = Partition(L, bottom, top);
		if (top - pivotpos < pivotpos - bottom){
			QuickSort(L, pivotpos + 1, top);
			QuickSort(L, bottom, pivotpos - 1);
		}
		else {
			QuickSort(L, bottom, pivotpos - 1);
			QuickSort(L, pivotpos + 1, top);
		}
	}
}
//heapsort
void HeapAdjust(SqList &L, int start, int top){
	L.data[0] = L.data[start];
	for (int i = 2 * start; i <= top; i *= 2){
		if (i < top && L.data[i].key > L.data[i+1].key){
			++i;
		}
		if (L.data[i].key < L.data[0].key){
			L.data[start] = L.data[i]; start = i;
		}
		else break;
	}
	L.data[start] = L.data[0];
}
void HeapSort(SqList &L){
	int len = L.length;
	for (int i = len / 2; i > 0; --i){
		HeapAdjust(L, i, len);
	}
	for (int i = len; i > 1; --i){
		L.data[0] = L.data[i];
		L.data[i] = L.data[1];
		L.data[1] = L.data[0];
		HeapAdjust(L, 1, i - 1);
	}
}
